#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;

int T=1;
int a[N];

int fan(char c){
    if(c=='0')return 1;
    else return 0;
}
void solve(){
    int n, x;cin>>n>>x;
    int m=x;
    string s;cin>>s;
    for(int i=0;i<n;i++)a[i]=0;
    if(x%2==1){
        for(int i=0;i<n;i++){
            if(s[i]=='1' && x!=0){
                a[i]=1;x--;
            }
            if(x==0)break;
        }
        if(x!=0)a[n-1]+=x;
    }
    else{
        for(int i=0;i<n;i++){
            if(s[i]=='0' && x!=0){
                a[i]=1;x--;
            }
            if(x==0)break;
        }
        if(x!=0)a[n-1]+=x;
    }
    for(int i=0;i<n;i++){
        if((m-a[i])%2==0)cout<<s[i];
        else cout<<fan(s[i]);
    }
    cout<<"\n";
    for(int i=0;i<n;i++)cout<<a[i]<<" ";
    cout<<"\n";
}

int main(){
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
